package william.array;

/**
 * @author ZhangShenao
 * @date 2024/4/13
 * @description <a href="https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode189_轮转数组 {
    /**
     * 1. 找到轮转的起点元素,即倒数第k个元素
     * 2. 记录需要轮转的k个元素
     * 3. 将不需要轮转的元素依次向后移动k个位置
     * 4. 将轮转的k个元素放到数组起始位置
     * 需要考虑k>数组长度的情况,即循环轮转,需要将k%数组长度
     * <p>
     * 时间复杂度O(N) 需要遍历一次数组
     * 空间复杂度O(1)
     */
    public void rotate(int[] nums, int k) {
        //边界条件校验
        if (nums == null || nums.length < 2 || k <= 0) {
            return;
        }

        int N = nums.length;

        //考虑k>数组长度的情况,即循环轮转,需要将k%数组长度
        k = (k % N);

        //找到轮转的起点元素,即倒数第k个元素
        int start = N - k;

        //记录需要轮转的k个元素
        int[] rotateEles = new int[k];
        for (int i = 0; i < k; i++) {
            rotateEles[i] = nums[start + i];
        }

        //将不需要轮转的元素依次向后移动k个位置
        for (int i = start - 1; i >= 0; i--) {
            nums[i + k] = nums[i];
        }

        //将轮转的k个元素放到数组起始位置
        for (int i = 0; i < k; i++) {
            nums[i] = rotateEles[i];
        }

    }
}
